#include <stdlib.h>
#include <string.h>
#include <stdio.h>

// NETWORK
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>

#include "topology.h"

// CONFIGURATION VARIABLES
#define MAX_HOST_NAME 256
#define ROUTE_COST 1

// ERROR MESSAGE MACROS
#define ERROR_POPULATE "error_populate: populate of forwarding table failed"

 // FORWARD TABLE ELEMENT STRUCTURE
typedef struct Table_Element
{
    Node_ID destination;
    Node_ID next_hop;
    int cost;

    // To implement the linked list
    struct Table_Element *next_element;

} Table_Element;

// FORWARD TABLE STRUCTURE
typedef struct Forward_Table
{
    Node_ID local;
    Table_Element *head;
    Table_Element *tail;
    int num_elements;

} Forward_Table;

Forward_Table* init_table(Forward_Table *table, Topology_Table *topo_table)
{
    table = malloc(sizeof(Forward_Table));

    table->local.IP = topo_table->local.IP;
    table->local.port = topo_table->local.port;

    table->head = NULL;
    table->tail = NULL;
    table->num_elements = 0;

    return table;
}

// Need to do a deep delete (TODO: FIX!)
void delete_table(Forward_Table *table)
{
    Table_Element *ptr = table->head;
    Table_Element *tmp;

    while(ptr != NULL)
    {
        tmp = ptr->next_element;
	free(ptr);
	ptr = tmp;
    }

    free(table);
}

// Adds an element to the end
Table_Element* add_element(Forward_Table *f_table, Node_ID *new_dest, Node_ID *new_next_hop, int cost)
{
    if (f_table->head == NULL){
        f_table->head = malloc(sizeof(Table_Element));
	f_table->tail = f_table->head;
    }

    else {
        f_table->tail->next_element = malloc(sizeof(Table_Element));
	f_table->tail = f_table->tail->next_element;
    }
    f_table->tail->destination.IP = new_dest->IP;
    f_table->tail->destination.port = new_dest->port;

    f_table->tail->next_hop.IP = new_next_hop->IP;
    f_table->tail->next_hop.port = new_next_hop->port;

    f_table->tail->cost = cost;
    f_table->tail->next_element = NULL;
    f_table->num_elements++;

    return f_table->tail;
}

// Adds an element to the end
Table_Element* super_add_element(Forward_Table *f_table, Table_Element*new_ptr)
{
    if (f_table->head == NULL){
        f_table->head = malloc(sizeof(Table_Element));
	f_table->tail = f_table->head;
    }

    else {
        f_table->tail->next_element = malloc(sizeof(Table_Element));
	f_table->tail = f_table->tail->next_element;
    }
    f_table->tail->destination.IP = new_ptr->destination.IP;
    f_table->tail->destination.port = new_ptr->destination.port;

    f_table->tail->next_hop.IP = new_ptr->next_hop.IP;
    f_table->tail->next_hop.port = new_ptr->next_hop.port;

    f_table->tail->cost = new_ptr->cost;
    f_table->tail->next_element = NULL;
    f_table->num_elements++;

    return f_table->tail;
}

// Removes an element to the table
void remove_element(Forward_Table *f_table, Node_ID *dead_dest, Node_ID *dead_next_hop)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    while(ptr != NULL)
    {
        // Check for match
        if (memcmp(&(ptr->destination.IP), &(dead_dest->IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->destination.port == dead_dest->port &&
            memcmp(&(ptr->next_hop.IP), &(dead_next_hop->IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->next_hop.port == dead_next_hop->port) {

            // Check to see if you are deleting the first element
            if (prev_ptr == NULL) {
                f_table->head = ptr->next_element;
	        free(ptr);
	    }

	    // Remove the element
	    else {

                prev_ptr->next_element = ptr->next_element;
	        free(ptr);
		ptr = prev_ptr->next_element;
	    }

            f_table->num_elements--;
            return;
	}

	else {

            // Increment the ptr
            prev_ptr = ptr;
            ptr = ptr->next_element;
	}
    }
}

// Removes an element to the table
void super_remove_element(Forward_Table *f_table, Table_Element *dead_ptr)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    while(ptr != NULL)
    {
        // Check for match
        if (memcmp(&(ptr->destination.IP),
                &(dead_ptr->destination.IP),
                sizeof(struct in_addr)) == 0 &&
                ptr->destination.port == dead_ptr->destination.port &&
            memcmp(&(ptr->next_hop.IP), &(dead_ptr->next_hop.IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->next_hop.port == dead_ptr->next_hop.port) {

            // Check to see if you are deleting the first element
            if (prev_ptr == NULL) {
                f_table->head = ptr->next_element;
	        free(ptr);
	    }

	    // Remove the element
	    else {

                prev_ptr->next_element = ptr->next_element;
	        free(ptr);
		ptr = prev_ptr->next_element;
	    }

            f_table->num_elements--;
            return;
	}

	else {

            // Increment the ptr
            prev_ptr = ptr;
            ptr = ptr->next_element;
	}
    }
}

// Finds the element in the forwarding table; returns the cost if found; -1 if not found
int contains_element(Forward_Table *f_table, Node_ID *dead_dest)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    while(ptr != NULL)
    {
        // Check for match
        if (memcmp(&(ptr->destination.IP), &(dead_dest->IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->destination.port == dead_dest->port) {

            return ptr->cost;
	}

	else {

            // Increment the ptr
            prev_ptr = ptr;
            ptr = ptr->next_element;
	}
    }
    return -1;
}

Table_Element* get_element(Forward_Table *f_table, Node_ID *dead_dest)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    while(ptr != NULL)
    {
        // Check for match
        if (memcmp(&(ptr->destination.IP), &(dead_dest->IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->destination.port == dead_dest->port) {

            return ptr;
	}

	else {

            // Increment the ptr
            prev_ptr = ptr;
            ptr = ptr->next_element;
	}
    }
    return NULL;
}

Node_ID* get_next_hop(Forward_Table *f_table, Node_ID *dest)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    while(ptr != NULL)
    {
        // Check for match
        if (memcmp(&(ptr->destination.IP), &(dest->IP),
                sizeof(struct in_addr)) == 0 &&
            ptr->destination.port == dest->port) {

            return &(ptr->next_hop);
	}

	else {

            // Increment the ptr
            prev_ptr = ptr;
            ptr = ptr->next_element;
	}
    }
    return NULL;
}

// Finds the element in the forwarding table; returns the cost if found; -1 if not found
Table_Element* smallest_element(Forward_Table *f_table)
{
    Table_Element *ptr = f_table->head;
    Table_Element *smallest = NULL;
    int smallest_cost = -1;


    while(ptr != NULL)
    {
        if (smallest_cost == -1){
            smallest_cost = ptr->cost;
            smallest = ptr;
        }

        else if (smallest_cost > ptr->cost){
            smallest_cost = ptr->cost;
            smallest = ptr;
        }

        // Increment the ptr
        ptr = ptr->next_element;
    }
    return smallest;
}

void dump_table(Forward_Table *f_table, char code)
{
    Table_Element *ptr = f_table->head;
    Table_Element *prev_ptr = NULL;

    if (code == 'F'){
        printf("\nFORWARD TABLE (%d)\ndest\t\t\tnext_hop\t\tcost\n----------------------------------------------------\n", f_table->num_elements);
    }

    else if (code == 'T'){
        printf("\nTENTATIVE (%d)\ndest\t\t\tnext_hop\t\tcost\n----------------------------------------------------\n", f_table->num_elements);
    }

    if (ptr == NULL) {
        printf("(empty)\n");
    }

    while(ptr != NULL)
    {
        print_Node_ID(&(ptr->destination));
        printf("\t");
        print_Node_ID(&(ptr->next_hop));
        printf("\t%d\n", ptr->cost);

        // Increment the ptr
        prev_ptr = ptr;
        ptr = ptr->next_element;
    }
    printf("\n");
}

// Based off of algorithm on page 257 of textbook
Forward_Table* build_table(Forward_Table *f_table, Topology_Table *topo_table)
{
    Table_Element *table_ptr = NULL;
    Table_Element *next = NULL;
    LSP_Packet *lsp_ptr = NULL;
    Node_ID *next_hop_ptr = NULL;

    Forward_Table *tentative = NULL;
    tentative = init_table(tentative, topo_table);

    // Step 1
    next = add_element(f_table, &(f_table->local), &(f_table->local), 0);

    // Easiest way to loop till table is complete
    while(1){

        // Step 2
        lsp_ptr = get_lsp(topo_table, &(next->destination));

	// Cycle through table until you find a valid lsp
	while(lsp_ptr == NULL) {

            if (tentative->num_elements <= 0) {

                dump_table(f_table, 'F');

                free(tentative);
                return f_table;
	    }

                next = smallest_element(tentative);
                next = super_add_element(f_table, next);
                super_remove_element(tentative, next);
        }

        //Step 3
        int i;
        for (i = 0; i < lsp_ptr->num_neighbors; i++){

            // Check to see we are neighbor to the local root
            if (memcmp(&(f_table->local.IP), &(lsp_ptr->source.IP),
                sizeof(struct in_addr)) == 0 &&
                f_table->local.port == lsp_ptr->source.port)  {

                next_hop_ptr = &(lsp_ptr->neighbors[i]);
            }

            else {
                next_hop_ptr = &(next->next_hop);
            }

            // Step 3a
            int new_cost = next->cost + ROUTE_COST;

            int f_table_cost = contains_element(f_table,
                                   &(lsp_ptr->neighbors[i]));

            int tentative_cost = contains_element(tentative,
                                   &(lsp_ptr->neighbors[i]));


            // Enactment of 3a
            if (f_table_cost == -1 && tentative_cost == -1) {

                table_ptr = add_element(tentative,
		        &(lsp_ptr->neighbors[i]), next_hop_ptr,
                        new_cost);
            }

            // Enactment of 3b
            else if (new_cost < tentative_cost) {

                Table_Element *to_remove = get_element(tentative, 
                                   &(lsp_ptr->neighbors[i]));
                super_remove_element(tentative, to_remove);

                table_ptr = add_element(tentative,
		        &(lsp_ptr->neighbors[i]), next_hop_ptr,
                        new_cost);
            }
        }

        // Uncomment for Debug
        // dump_table(f_table, 'F');
        // dump_table(tentative, 'T');

        // Step 4
        if (tentative->num_elements == 0){

            dump_table(f_table, 'F');
            //dump_table(tentative, 'T');

            free(tentative);
            return f_table;
        }

        else{
            next = smallest_element(tentative);
            next = super_add_element(f_table, next);
            super_remove_element(tentative, next);
        }

        // Uncomment for Debug
        // dump_table(f_table, 'F');
        // dump_table(tentative, 'T');
    }

    // Should never reach here
    return NULL;
}

